package _11_整理题目._3_字符串_递归_dfs_bfs_双指针._矩阵搜索;

import org.junit.Test;

import java.util.Arrays;

/**
 * https://leetcode-cn.com/problems/longest-increasing-path-in-a-matrix/
 *
 * 给定一个 m x n 整数矩阵 matrix ，找出其中 最长严格递增路径 的长度。
 * 对于每个单元格，你可以往上，下，左，右四个方向移动。
 * 不能 在 对角线 方向上移动或移动到 边界外（即不允许环绕）。
 *
 * 思路一：dfs
 *      遍历每一个单元格，以此为起点，不断地向四周搜索比当前单元格大的单元格，
 *      再以下一个单元格 为起点，重复上述过程的同时不断更新从最初的起点到当前单元格的最长递增距离。
 *      缺点：会有很多位置重复计算
 *
 * 思路二：dfs + 记忆化搜索
 *      在思路一的基础上，记录每一个位置的 最长路径，后面遍历到之前的记录时直接使用
 *      增加一个 memory 二维数组
 */
public class _30_矩阵中最长递增路径 {

    private int m = 0;
    private int n = 0;
    private int max = 0;

    public int longestIncreasingPath(int[][] matrix) {
        m = matrix.length;
        n = matrix[0].length;
        for(int i=0; i<m; i++) {
            for(int j=0; j<n; j++) {
                dfs(matrix, i, j, -1, 0);
            }

        }
        return max;
    }

    public void dfs(int[][] matrix, int i, int j, int num, int count) {
        if(i<0 || i>=m || j<0 || j>=n || matrix[i][j] <= num) {
            max = Math.max(max, count);
            return;
        }

        dfs(matrix, i+1, j, matrix[i][j], count+1);
        dfs(matrix, i-1, j, matrix[i][j], count+1);
        dfs(matrix, i, j+1, matrix[i][j], count+1);
        dfs(matrix, i, j-1, matrix[i][j], count+1);
    }

    @Test
    public void main() {
        int[][] matrix = {
                {9, 9, 4},
                {6, 6, 8},
                {2, 1, 1},
        };
        System.out.println(longestIncreasingPath(matrix)); // 4: 1 2 6 9
    }
}
